package String;

public class _647_PalindromicSubstrings {
    int totalCount = 0;
    //too slow,O(n^3)
    public int countSubstrings(String s) {
        char[] ch = s.toCharArray();
        for(int i=0;i<ch.length;i++) {
            getCount(ch,i,i,ch.length-1);
        }
        return totalCount;
    }

    public void getCount(char[] ch, int start,int end,int last) {
        if (last < end) {
            return;
        } else {
            int tempStart = start,tempEnd = end;
            boolean palin = true;
            while (tempStart < tempEnd) {
                if (ch[tempStart] != ch[tempEnd]) {
                    palin = false;
                    break;
                }
                tempStart++;
                tempEnd--;
            }
            if (palin) {
                totalCount++;
            }
            getCount(ch,start, end + 1,last);
        }
    }

    //reference faster solution,

    /**
     * begin from the middle of the arrary to the edge,not circle from start to end,O(n^2)
     * @param s
     * @return
     */
    public int countSubstrings1(String s) {

        char[] chars = s.toCharArray();
        int count = 0;
        for(int i = 0; i < chars.length; ++i) {
            count += getPalindromeCount(chars, i, i);
            count += getPalindromeCount(chars, i, i+1);
        }

        return count;
    }

    public int getPalindromeCount(char[] chars, int start, int end) {
        int count = 0;

        while(start >= 0 && end < chars.length && chars[start] == chars[end]) {
            --start;
            ++end;
            ++count;
        }

        return count;
    }
}
